/**
 * https://leetcode.cn/problems/maximum-subarray/submissions/546585034/
 * 53. 最大子数组和
 * medium 2024.07.14
 * 前缀和后缀和差分
 */

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int r=nums.size()-1;
        int k=r;
        if(r==0)
        return nums[r];
        int suml=0;
        int sumr=0;
        int smm=0;
        int maxt=-10e4-5;
        int l;
        for(l=0;l<r;l++,r--){
            suml+=nums[l];
            sumr+=nums[r];
            if(suml<0)
                suml=0;
            if(suml>smm)
                smm=suml;
            if(sumr<0)
                sumr=0;
            if(sumr>smm)
                smm=sumr;
            maxt=max({maxt,nums[l],nums[r]});
        }
        if(l==r){
            if(suml+nums[l]<0)
            suml=0;
            else if(sumr+nums[l]<0)
            sumr=0;
            else
            sumr+=nums[l];
            maxt=max(maxt,nums[l]);
        }
        if(smm>suml+sumr)
        return smm;
        if(maxt<0)
        return maxt;
        return suml+sumr;
    }
};